This invention relates to a method and apparatus for the lossless compression of data.
While lossy data compression hardware has been available for image and signal processing for some years, lossless data compression has only recently become of interest, as a result of increased commercial pressure on bandwidth and cost per bit in data storage and data transmission; also, reduction in power consumption by reducing data volume is now of importance.
The principles of searching a dictionary and encoding data by reference to a dictionary address is well known, and the apparatus to apply the principle consists of a dictionary and a coder/decoder.
In Proceedings of EUROMICRO-22, 1996, IEEE, xe2x80x9cDesign and Performance of a Main Memory Hardware Data Compressorxe2x80x9d, Kjelso, Gooch and Jones describe a novel compression method, termed the X-Match algorithm, which is efficient at compressing small blocks of data and suitable for high speed hardware implementation.
The X-Match algorithm maintains a dictionary of data previously seen, and attempts to match a current data element, referred to as a tuple, with an entry in the dictionary, replacing a matched tuple with a shorter code referencing the match location. The algorithm operates on partial matching, such as 2 bytes in a 4 byte data element. In Proceedings of EUROMICRO-25, 1999, IEEE, xe2x80x9cThe X-MatchLITE FPGA-Based Data Compressorxe2x80x9d, Nunez, Feregrino, Bateman and Jones describe the X-Match algorithm implemented in a Field Programmable Gate Array (FPGA) prototype.
It is an object of the invention to provide a lossless data compression algorithm which can compress data at a faster rate than is possible with the published arrangement.
According to the invention a lossless data compression system comprising a dictionary based on content addressable memory and a coder having between them a feedback loop forming a dictionary adaptation path, characterised by register means connected in the feedback loop whereby the dictionary can be updated using data from a previous comparison cycle at the same time as the coder codes a current comparison cycle.
Also according to the invention, a lossless method of compressing data comprising the steps of:
comparing a search tuple of fixed length with a plurality of tuples of said fixed length stored in a dictionary;
indicating the location in the dictionary of a full or partial match or matches;
selecting a best match of any plurality of matches; and
encoding the match location and the match type;
characterised by the further steps of:
providing the dictionary with a current adaptation vector and a next adaptation vector;
and after comparison of each search tuple
(a) updating the contents of the dictionary in accordance with the current adaptation vector and
(b) updating the next adaptation vector in accordance with the current adaptation vector.